package com.algo.tree;

import org.junit.Test;

import javax.xml.crypto.NodeSetData;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class BinaryTree {
    public Node root;

    @Test
    public void test() {
        Integer[] a = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        insertArray(a);
        tierOrder();
        System.out.println();
        System.out.println(a[findParent(a, 8)]);
    }

    public int findParent(Integer[] list, int value) {
        int a = -1, result = -1;
        for (int i = 0; i < list.length; i++) {
            if (list[i].equals(value)) {
                a = (i);
                break;
            }
        }
        if (a != -1) {
            if (a % 2 == 1) {
                result = a / 2;
            } else {
                result = (a - 1) / 2;
            }
        }
        return result;
    }


    public void insertArray(Integer[] arr) {
        ArrayList<Node> list = new ArrayList<>();
        if (root == null) {
            root = new Node(arr[0]);
        }
        list.add(root);
        for (int i = 1; i < arr.length; i++) {
            Node tmp = list.get(0);
            if (tmp == null) {
                if (i % 2 == 1) {
                    continue;
                } else {
                    list.remove(0);
                    continue;
                }
            }
            if (i % 2 == 1) {
                Node<Integer> left = new Node<>(arr[i]);
                tmp.left = left;
                list.add(left);
            } else {
                Node<Integer> right = new Node<>(arr[i]);
                list.remove(0);
                tmp.right = right;
                list.add(right);
            }
        }
    }

    //层序遍历
    public void tierOrder() {
        if (root == null) {
            throw new NullPointerException("root节点为空");
        }
        LinkedList<Node> list = new LinkedList<>();
        list.push(root);
        while (!list.isEmpty()) {
            Node headNode = list.poll();
            System.out.print(headNode.value + ",");
            if (headNode.left != null) {
                list.offer(headNode.left);
            }
            if (headNode.right != null) {
                list.offer(headNode.right);
            }
        }
    }


    //先序遍历
    public void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }


    public class Node<T> {
        T value;
        Node left;
        Node right;

        public Node(T value) {
            this.value = value;
        }
    }
}
